package com.xiaojianhx.demo.algorithm.sort;

/**
 * 07 归并排序
 * 
 * @author xiaojianhx
 * @version V1.0.0 $ 2021-08-04 22:42:31 init ---- xiaojianhx
 */
public class Algorithm_Sort_07_MergeSort {

    public static void sort(int[] a) {
        sort(a, 0, a.length - 1);
    }

    private static void sort(int[] a, int low, int hight) {

        var mid = (low + hight) / 2;

        if (low < hight) {
            sort(a, low, mid);
            sort(a, mid + 1, hight);
            System.out.println("low == " + low + ", mid == " + mid + ", hight == " + hight);
            merge(a, low, mid, hight);
        }
    }

    private static void merge(int[] a, int low, int mid, int hight) {

        var tmp = new int[hight - low + 1];
        var l = low;
        var m = mid + 1;
        var k = 0;

        // 把较小的数先移到新数组中（插入排序）
        while (l <= mid && m <= hight) {
            tmp[k++] = a[l] < a[m] ? a[l++] : a[m++];
        }

        // 把左边剩余的数移入数组
        while (l <= mid) {
            tmp[k++] = a[l++];
        }

        // 把右边边剩余的数移入数组
        while (m <= hight) {
            tmp[k++] = a[m++];
        }

        // 回填
        for (var i = 0; i < tmp.length; i++) {
            a[i + low] = tmp[i];
        }
    }
}